package com.nanxhs.structure.tree;

import java.util.Objects;

/**
 * 二叉查找树
 * @author 唐海斌
 * @version 1.0
 * @date 2021/5/24 10:44
 */
public class BinarySearchTree extends Tree {

    @Override
    public void add(int element) {
        TreeNode newNode = new TreeNode();
        newNode.setElement(element);
        if (root == null) {
            newNode.setElement(element);
            root = newNode;
            return;
        }
        add(newNode, root);
    }

    private void add(TreeNode newNode, TreeNode parentNode) {
        TreeNode childrenLeft = parentNode.getChildrenLeft();
        TreeNode childrenRight = parentNode.getChildrenRight();
        Integer parentElement = parentNode.getElement();
        Integer newElement = newNode.getElement();
        if (Objects.equals(parentElement, newElement)) {
            return;
        }
        if (newElement < parentElement) {
            if (childrenLeft == null) {
                newNode.setParent(parentNode);
                parentNode.setChildrenLeft(newNode);
                return;
            }
            add(newNode, childrenLeft);
        } else {
            if (childrenRight == null) {
                newNode.setParent(parentNode);
                parentNode.setChildrenRight(newNode);
                return;
            }
            add(newNode, childrenRight);
        }
    }

    /**
     * 删除元素
     * @param element
     */
    @Override
    public void remove(int element) {
        remove(element, root);
    }

    /**
     * 删除枝干节点
     *     节点下有左右子树
     *         如果节点在树干的左边
     *             左子节点替换删除的节点，更改右节点的指向
     *          如果节点在树干的左边
     *             右子节点替换删除的节点，更改左节点的指向
     *     节点下只有左子树
     *         左子树直接替换
     *     节点下只有右子树
     *         右子树直接替换
     * 删除叶子节点
     *     直接删除
     * @param element
     * @param currentNode
     */
    private void remove(int element, TreeNode currentNode) {
        if (currentNode == null) {
            return;
        }
        TreeNode childrenLeft = currentNode.getChildrenLeft();
        TreeNode childrenRight = currentNode.getChildrenRight();
        if (Objects.equals(element, currentNode.getElement())) {
            //叶子节点
            if (childrenLeft == null && childrenRight == null) {
                if (currentNode.getParent().getChildrenLeft() == currentNode) {
                    currentNode.getParent().setChildrenLeft(null);
                }
                if (currentNode.getParent().getChildrenRight() == currentNode) {
                    currentNode.getParent().setChildrenRight(null);
                }
                return;
            }
            //只有左子树
            if (childrenLeft != null && childrenRight == null) {
                if (currentNode.getParent().getChildrenLeft() == currentNode) {
                    childrenLeft.setParent(currentNode.getParent());
                    currentNode.getParent().setChildrenLeft(childrenLeft);
                }
                return;
            }
            //只有右子树
            if (childrenLeft == null && childrenRight != null) {
                if (currentNode.getParent().getChildrenRight() == currentNode) {
                    childrenRight.setParent(currentNode.getParent());
                    currentNode.getParent().setChildrenRight(childrenRight);
                }
                return;
            }
            //同时存在左右子树
            if (currentNode.getParent().getChildrenLeft() == currentNode) {
                currentNode.getParent().setChildrenLeft(childrenLeft);
                childrenLeft.setParent(currentNode.getParent());
                childrenLeft.setChildrenRight(childrenRight);
                childrenRight.setParent(childrenLeft);
                return;
            }
            if (currentNode.getParent().getChildrenRight() == currentNode) {
                currentNode.getParent().setChildrenRight(childrenRight);
                childrenRight.setParent(currentNode.getParent());
                childrenRight.setChildrenLeft(childrenLeft);
                childrenLeft.setParent(childrenRight);
            }
            return;
        }
        remove(element, childrenLeft);
        remove(element, childrenRight);
    }
}
